In various fields, demands exist for searching for desired fixed-length data from a database at high speed. In particular, in databases used for intra-network relay apparatuses or inter-network relay apparatuses to perform relay-destination determination and relay determination, when a different search rule is used, more-enhanced requirements exist for high-speed searching operation, efficient database construction/management and so on, and database reading/modification and so on after searching.
Related technologies for searching a database at high speed are used for searching MAC (media access control) address tables. Examples of the related technologies for searching a MAC address table include a method applying a hash function, a method using a CAM (content addressable memory) and other methods, such as a method using a two-way searching algorithm. When a MAC address table is configured with hundreds of thousand of MAC addresses or more, there are the following problems.
To search for desired fixed-length data from a database, there is a known search method in which desired fixed-length data exactly matches fixed-length data in the database. Many search methods using other search rules are implemented and used in practice. For example, searching for a desired IP (Internet Protocol) address from a routing table used by an inter-network relay apparatus requires searching based on an LPM (longest prefix matching) method. An IP address is constituted by a network address (also called a prefix) and a host address. Prefixes have variable lengths and are aggregated. The aggregation refers to representing multiple prefixes having the same address and common high-order bits of the prefixes as one prefix. The representative prefix is expressed by the common high-order bits. As a result, when a routing table containing an aggregated IP address is searched, matching of multiple IP addresses occurs. The LPM method is a search method that uses, as a search result, the longest prefix of matched IP addresses. A related technology that realizes high-speed searching based on the LPM method is TCAM (Ternary Content Addressable Memory). TCAM can achieve high-speed searching but has the same problem as the above-noted CAM. That is, with TCAM, it is difficult to manufacture large-scale (large-capacity) TCAMs due to the circuit structure, and TCAMs cannot hold a large amount of fixed-length data.
A rule of searching with a mask function is commonly used. With this rule, for example, to search for desired fixed-length data from a database, when the desired fixed-length data matches part (or maybe all) of the fixed-length data in the database, the matched part is used as a search result. In this case, the mask has the same data length as the fixed-length data and has a capability of masking fixed-length data bit by bit. Many search methods have been implemented under this search rule. This rule will be described in accordance with an example of an intra-network relay apparatus and an inter-network relay apparatus. The apparatus of this example searches a routing table to determine to which transmission port packets are output. In this case, whether or not to transmit packets is determined by a filtering function. This filtering function is a typical example of searching with a mask function. For example, for an input packet, the filtering function uses a flow table configured with 104-bit fixed-length data including five types of data, namely, a source IP address (32 bits), a destination IP address (32 bits), a protocol (8 bits), a source port (16 bits), and a destination port (16 bits). In this case, some of the 104 bits can be excluded (masked) from targets for comparison, and fixed-length data whose all unmasked bits shows a match is used as a search result. The related technology using searching with a mask function generally employs a hash method or CAM. The hash method and CAM also have the following problems.
Specifically, a major problem of the search system of the related technology is configuring and managing a database. To select or implement various search methods, the method for configuring and managing a database must also be evaluated to realize an intended search system.
Problems in database configuration and management in the related technology will be described in conjunction with a search method employing, by way of example, a quick search based on two-way searching and TCAM. In the two-way search method, first, a database in which m pieces of fixed-length data, which are constituent members of the database, are arranged in order of size is prepared. Fixed-length data located at the database midpoint [m/2] (when m is an odd number, [m/2] means obtaining an integer by rounding-off) and fixed-length data to be searched for are compared with each other, thereby starting the search. As a result of the comparison, when the fixed-length data to be searched for is larger, fixed-length data located at the midpoint of [m/2] and m, that is, [([m/2]+m)/2], and the fixed-length data to be searched for are compared with each other. When the first comparison shows that the fixed-length data to be searched for is smaller, fixed-length data located at the midpoint of [m/2] and 1, that is, [([m/2]+1)/2], and the fixed-length data to be searched for are compared with each other. When the fixed-length data compared with the fixed-length data to be searched for shows a match, the compared fixed-length data becomes the search result and the search finishes. The above-described comparison operation is performed as long as the midpoint calculation is possible. However, when the midpoint calculation is performed with 1 and 2, 1 is selected to perform comparison. When m is 262,144 (2 raised to the 18th power), up to 18+1 reading operations from the database are required. Since the above-described search operation is simple, this search method is feasible. However, configuring and managing the database is not simple. In particular, when m becomes large, as in the above-described example, and a typical large-scale database is configured for a communication control apparatus, a large amount of time and a great computational capability are required. In addition, under the recent environment where mobile products are more prevalent and where changes must be made to databases over time, fixed-length data are frequently deleted from or added to the databases. Each time fixed-length data is deleted or added in the related technologies, the above-noted rearrangement must be performed. In this manner, under the current situation, the configuration and management of databases is a great burden and is a large obstacle to the search capabilities.
In the related technologies, TCAM is often used as a method for searching for an IP address at high speed. TCAM, however, has the same problem as CAM. The memory capacity is not as large as that of a DRAM (dynamic random access memory). Thus, when a database including a large number of IP addresses is configured, a large number of TCAMs are required, and a large database cannot be configured due to power-supply and packaging restrictions. In addition, the use of TCAM causes a problem in configuring and managing a database. With the LPM rule, many pieces of fixed-length data that match desired fixed-length data exist, as described above. In order to select fixed-length data having the longest prefix from those pieces of fixed-length data, it is necessary to arrange the many pieces of matched fixed-length data in order of prefix lengths thereof. That is, a task for grouping a collection of IP addresses having common high bits and arranging the IP addresses in a group in order of lengths is required as a task for configuring the database. In this case, in order to minimize the influence on the search performance after changes are made, it is necessary to prepare some empty locations across the groups for an additional operation, with an aim to complete the additional operation in a minimum period of time. In this manner, when TCAM is used, configuring and managing the database without a reduction in the search performance involves a major problem. The preparation of some empty locations across the groups results in a vicious circle in which the use efficiency of the TCAM is reduced, thus causing a further reduction in the capacity of the TCAM.
Communication control apparatuses typically have functions for, after searching a database, reading user data at a destination port or the like from its search result and modifying statistical data of the matched fixed-length data. In the high-speed search methods of the related technologies, user data, statistical data, and so on are stored in an external memory device; therefore, a large amount of time is required from commencing the search to obtaining a destination port.